# Author: Yu Bin
# Date: 2025/01/02 10:51:12
# E-mail: 853823259@qq.com
class Node:
    """
    节点类
    """

    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class BinaryTree:
    def __init__(self):
        self.root = None
        self.help_queue = []  # 辅助队列

    def level_build_tree(self, node: Node):
        """
        层序建树
        :param node:
        :return:
        """
        if self.root is None:  # 树根为空
            self.root = node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if self.help_queue[0].lchild is None:
                self.help_queue[0].lchild = node
            else:
                self.help_queue[0].rchild = node
                self.help_queue.pop(0)  # 当前父亲满了，出队

    def pre_order(self, current_node: Node):
        """
        先序遍历
        :param current_node:
        :return:
        """
        if current_node:
            print(current_node.elem, end=' ')
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def mid_order(self, current_node: Node):
        """
        中序遍历
        :param current_node:
        :return:
        """
        if current_node:
            self.mid_order(current_node.lchild)
            print(current_node.elem, end=' ')
            self.mid_order(current_node.rchild)

    def level_order(self):
        """
        层序遍历
        :return:
        """
        help_queue = []
        help_queue.append(self.root)
        while help_queue:
            out_node: Node = help_queue.pop(0)
            print(out_node.elem, end=' ')
            if out_node.lchild:
                help_queue.append(out_node.lchild)
            if out_node.rchild:
                help_queue.append(out_node.rchild)


if __name__ == '__main__':
    tree = BinaryTree()
    for i in range(1, 11):
        new_node = Node(i)
        tree.level_biuld_tree(new_node)  # 把节点放入树中
    print("前序遍历：")
    tree.pre_order(tree.root)
    print("\n中序遍历：")
    tree.mid_order(tree.root)
    print("\n层序遍历：")
    tree.level_order()
